import java.util.*;

// 力扣380. O(1) 时间插入、删除和获取随机元素
class RandomizedSet {

    Map<Integer,Integer> map; // 存 插入的值 和对应的 顺序表下标(方便查询,时间复杂度为O(1))
    Random random; // 生成随机数
    List<Integer> list; // 存 插入的值

    public RandomizedSet() {
        map = new HashMap<>();
        random = new Random();
        list = new ArrayList<>();
    }

    public boolean insert(int val) {
        if(map.containsKey(val)){
            return false;
        }
        list.add(val);
        map.put(val,list.size()-1);
        return true;
    }

    public boolean remove(int val) {
        if(!map.containsKey(val)){
            return false;
        }
        int index = map.get(val); // 获取 当前要移除的元素 的下标
        int lastNum = list.get(list.size()-1); // 获取顺序表的 最后一个元素
        list.set(index,lastNum); // 将 当前要移除的元素 的下标设为最后一个元素的值
        map.put(lastNum,index); // 更新 map 中顺序表的 最后一个元素 的值的下标
        list.remove(list.size()-1); // 删除 最后一个元素
        map.remove(val); // 删除 对应的元素
        return true;
    }

    public int getRandom() {
        // 生成 [0,list.size()-1) 的数
        int res = random.nextInt(list.size());
        return list.get(res);
    }
}


// 力扣274. H 指数
class Solution {
    public int hIndex(int[] citations) {
        // 数组中有h个不小于h的值，求最大的h
        Arrays.sort(citations);
        int n = citations.length;
        for(int i = 0; i < n; i++){
            if(citations[i] >= n - i){
                return n - i;
            }
        }
        return 0;
    }
}